package com.lmk.dsa.algorithm.graph.miniTree;

import java.util.ArrayList;
import java.util.List;
import com.lmk.dsa.struct.commons.Edge;
import com.lmk.dsa.struct.commons.KvNode;
import com.lmk.dsa.struct.graph.Graph;
import com.lmk.dsa.struct.heap.MinHeap;

/**
 * LazyPrim算法
 * @author LaoMake
 * @since 1.0
 */
public class LazyPrim {

    /** 图的引用 */
    private Graph graph;

    /** 顶点的总数 */
    private int n;

    /** 访问状态数组 */
    private boolean[] marked;

    /** 用于存储边的最小堆 */
    private MinHeap heap;

    /** 最小生成树的边 */
    private List<Edge> edgeList;

    /** 最小生成树的总权值 */
    private int miniWeight;

    public LazyPrim(Graph graph) {
        this.graph = graph;
        this.miniWeight = 0;
        this.n = graph.vertexSize();
        this.heap = new MinHeap(graph.edgeSize());
        this.marked = new boolean[n];
        this.edgeList = new ArrayList<>(n - 1);
    }

    public int getMiniWeight() {
        return miniWeight;
    }

    public List<Edge> miniTree(){
        lazyPrimVisit(0);
        KvNode<Integer, Edge> node;
        Edge edge;
        while (heap.size() > 0){
            node = heap.pool();
            edge = node.value;
            if (marked[edge.from] == marked[edge.to])
                continue; // 忽略非横切边

            edgeList.add(edge);
            if(!marked[edge.from]){
                lazyPrimVisit(edge.from);
            }else{
                lazyPrimVisit(edge.to);
            }
        }

        for (Edge e : edgeList){
            miniWeight += e.weight;
        }
        return edgeList;
    }

    private void lazyPrimVisit(int v){
        List<Edge> edges;
        if(!marked[v]){
            marked[v] = true;
            edges = graph.adjoinEdge(v);
            for (Edge edge : edges){
                // 当这条边的另外一节点未被访问，说明这是一条横切边
                if(!marked[edge.other(v)]){
                    heap.add(edge.weight, edge);
                }
            }
        }
    }



}
